package demo10;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-26
 * Time: 17:41
 */
public class HeapGreaterTest<T> {

    public ArrayList<T> heap;//数组
    public HashMap<T,Integer> indexMap;//反向索引表
    public int heapSize;//有效个数
    public Comparator<? super T> comparator;
    public HeapGreaterTest(Comparator<? super T> c1){
        this.heap = new ArrayList<>();
        this.indexMap = new HashMap<>();
        this.heapSize = 0;
        this.comparator = c1;
    }

    //判断是否为空
    public boolean isEmpty(){
        return heapSize==0;
    }

    //获取到数组大小
    public int Size(){
        return this.heapSize;
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    //peek push pop remove resign heapify  heapInsert swap

    public T peek(){
        return heap.get(0);
    }

    public void push(T obj){
        //将obj对象插入到堆中,同时添加到反向索引表中
        heap.add(obj);
        indexMap.put(obj,heapSize);
        heapInsert(heapSize++);//将最后一个元素向上调整
    }

    public void heapInsert(int index){
        while(index > 0&&comparator.compare(heap.get(index),heap.get((index - 1)/2))>0){
             swap(index,(index-1)/2);
             index = (index - 1)/2;
        }
    }


    public  void swap(int i,int j){
        T a = heap.get(i);
        T b = heap.get(j);
        heap.set(j,a);
        heap.set(i,b);
        indexMap.put(a,j);
        indexMap.put(b,i);
    }

    //pop remove resign heapify



}
